//给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。 
//
// 返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 
//最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。 
//
// 示例 1： 
//
// 
//输入：
//[
//   [1,0,1],
//   [0,0,1],
//   [0,0,1]
//]
//输出：[1,0,2]
//解释：输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
// 
//
// 示例 2： 
//
// 
//输入：
//[
//   [0,1,1],
//   [1,0,1],
//   [1,1,0]
//]
//输出：[0,0,1]
// 
//
// 提示： 
//
// 
// matrix.length == matrix[0].length <= 200 
// 
//
// Related Topics 数组 动态规划 矩阵 👍 60 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-09-21 17:37:23
 * @description 面试题 17.23.最大黑方阵
 */
public class MaxBlackSquareLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MaxBlackSquareLcci fun=new MaxBlackSquareLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int[] findSquare(int[][] matrix) {
		int n = matrix.length;
		//left[i][j]: 表示从位置 (i-1, j-1) 开始向左连续有多少个 0
		//up[i][j]: 表示从位置 (i-1, j-1) 开始向上连续有多少个 0
		int[][] left = new int[n + 1][n + 1];
		int[][] up = new int[n + 1][n + 1];
		int r = 0, c = 0, size = 0;
		//遍历每个位置 (i, j),检查他的左边和上边的连续 0 的数量
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				//如果 matrix[i-1][j-1] == 0（当前位置是0）
				//left[i][j] = left[i][j-1] + 1（左边的连续0数+1）
				//up[i][j] = up[i-1][j] + 1（上边的连续0数+1）
				if (matrix[i - 1][j - 1] == 0) {
					left[i][j] = left[i][j - 1] + 1;
					up[i][j] = up[i - 1][j] + 1;
					//计算可能的边长：border = min(left[i][j], up[i][j])
					//验证这个正方形是否有效：
					//检查左边：left[i - border + 1][j] >= border
					//检查上边：up[i][j - border + 1] >= border
					int border = Math.min(left[i][j], up[i][j]);
					//因为下边和右边是满足的，不断缩小左边和上边边长，直到找到满足条件的边长
					while (left[i - border + 1][j] < border || up[i][j - border + 1] < border) {
						border--;
					}
					//更新最大边长和位置
					if (border > size) {
						r = i - border;
						c = j - border;
						size = border;
					}
				}
			}
		}
		return size > 0 ? new int[]{r, c, size} : new int[0];
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
